home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Programming Contest / ~Solutions Submitted / Problem 02 - Three and One / Solution.cp < prev    next >
Encoding:
Text File  |  1998-06-19  |  6.1 KB  |  227 lines  |  [TEXT/CWIE]
  1. /*
  2. Problem 02 - Hower of Tanoi
  3.  
  4. This problem is to solve a variant of the Tower of Hanoi puzzle.  You remember
  5. the Tower of Hanoi, a board with three pegs, one of which has N disks of size
  6. 1, 2, 3, ... N, with the smallest disk at the top.  In the standard puzzle, the
  7. goal is to move all of the disks from one peg to another peg, by repeatedly
  8. moving a disk from the top of one peg to another peg without ever placing a
  9. larger disk on top of a smaller disk.
  10.  
  11. In our Hower of Tanoi problem, the objective and the constraints are the same,
  12. except that the disks on the first peg are initially in random order. You can
  13. still only move a smaller disk onto a larger disk.
  14.  
  15. Your objective is output the moves required to place all the disks on peg 3 in
  16. order with the smallest disk at the top.  
  17.  
  18. Input specification
  19.  
  20. The first line of the input file contains an integer M, M<1000, the number of
  21. disks in the problem.  The next M lines contain the numbers 1 .. M, one number
  22. per line, randomly ordered, where the first number is the size of the top disk
  23. on peg 1, the second number is the size of the 2nd disk from the top, etc.
  24.  
  25. Output specification
  26.  
  27. The output is a sequence of lines, each representing a single move,  consisting
  28. of the source peg number followed by a comma (',') followed by the destination
  29. peg number, followed by a return character.
  30.  
  31. Sample input
  32.  
  33. 2
  34. 2
  35. 1
  36.  
  37. Sample output
  38.  
  39. 1,3
  40. 1,3
  41. */
  42.  
  43. #undef DEBUG
  44. #define NDEBUG
  45.  
  46. #include "Solution.h"
  47. #include <assert.h>
  48. #include <string>
  49. #include <sstream>
  50. #include <stdio.h>
  51.  
  52. // Fill in your solution and then submit this folder
  53.  
  54. // Team Name: ThreeAndOne
  55.  
  56. struct Tower
  57. {
  58.     int length;
  59.     int disks[1000];    // Array of length disks in order from bottom to top
  60.  
  61.     int popDisk() {assert(length); return disks[--length];}
  62.     void pushDisk(int disk) {assert(!length || disks[length-1] > disk); disks[length++] = disk;}
  63.     int largestDisk(int depth, int &pos);
  64.     bool ordered(int depth);
  65.     int diskAtDepth(int depth) {assert (depth < length); return disks[length - 1 - depth];}
  66. };
  67.  
  68. Tower ReadTower(short refNum)
  69. {
  70.     long eof;
  71.     GetEOF(refNum, &eof);
  72.     char* buffer = new char[eof];
  73.     FSRead(refNum, &eof, buffer);
  74.     std::string asstring(buffer, eof);
  75.     delete [] buffer;
  76.     std::istringstream s(asstring);
  77.     
  78.     Tower tower;
  79.     s >> tower.length;
  80.     int index = tower.length;
  81.     while (index != 0)
  82.         s >> tower.disks[--index];
  83.     return tower;
  84. }
  85.  
  86. short outRef;
  87. void WriteMove(int from, int to)
  88. {
  89.     std::ostringstream s;
  90.     s << from << "," << to;
  91.     long count = s.str().size();
  92.     FSWrite(outRef, &count, s.str().data());
  93.     count = 1;
  94.     char CR = 13;
  95.     FSWrite(outRef, &count, &CR);
  96. }
  97.  
  98. int Tower::largestDisk(int depth, int &pos)
  99. {
  100.     assert(depth <= length);
  101.     pos = 0;
  102.     int largest = 0;
  103.     for (int i = 0; i != depth; i++)
  104.         if (disks[length-1-i] > largest) {
  105.             largest = disks[length-1-i];
  106.             pos = i;
  107.         }
  108.     return largest;
  109. };
  110.  
  111. bool Tower::ordered(int depth)
  112. {
  113.     if (depth == 0)
  114.         return true;
  115.     int disk = disks[length-1];
  116.     for (int i = 1; i != depth; i++) {
  117.         int d = disks[length-1-i];
  118.         if (d <= disk)
  119.             return false;
  120.         disk = d;
  121.     }
  122.     return true;
  123. }
  124.  
  125.  
  126. struct Emitter
  127. {
  128.     Tower pegs[3];
  129.  
  130.     void moveDisk(int srcPeg, int dstPeg);
  131.     void moveTower(int srcPeg1, int srcPeg2, int dstPeg, int depth1, int depth2, int depth3);
  132.     Tower &peg(int n) {assert(n>=1 && n<=3); return pegs[n-1];}
  133. };
  134.  
  135.  
  136. #ifdef DEBUG
  137. static int callDepth = 0;
  138. #endif
  139.  
  140. void Emitter::moveDisk(int srcPeg, int dstPeg)
  141. {
  142.   #ifdef DEBUG
  143.     for (int z = callDepth; z; z--)
  144.         fprintf(stderr, "  ");
  145.     fprintf(stderr, "moveDisk %d -> %d\n", srcPeg, dstPeg);
  146.   #endif
  147.     assert(srcPeg != dstPeg);
  148.     peg(dstPeg).pushDisk(peg(srcPeg).popDisk());
  149.   #ifdef DEBUG
  150.     for (int peg = 0; peg != 3; peg++) {
  151.         Tower &tower = pegs[peg];
  152.         fprintf(stderr, " [");
  153.         for (int i = 0; i != tower.length; i++)
  154.             fprintf(stderr, "%d ", tower.disks[i]);
  155.         fprintf(stderr, "] ");
  156.     }
  157.     fprintf(stderr, "\n");
  158.   #endif
  159.     WriteMove(srcPeg, dstPeg);
  160. }
  161.  
  162. // Merge the top depth1 disks on srcPeg1 with the top depth2 disks on srcPeg2 and
  163. // the top depth3 disks on dstPeg and put them onto dstPeg.
  164. // The disks on srcPeg1 are in any order, but the disks on srcPeg2 and dstPeg
  165. // must be in proper size order.  Any disks below the top depth1 disks on
  166. // srcPeg1, top depth2 disks on srcPeg2, and top depth3 disks on dstPeg don't affect
  167. // the possible moves.
  168. void Emitter::moveTower(int srcPeg1, int srcPeg2, int dstPeg, int depth1, int depth2, int depth3)
  169. {
  170.   #ifdef DEBUG
  171.     for (int z = callDepth; z; z--)
  172.         fprintf(stderr, "  ");
  173.     fprintf(stderr, "moveTower %d:%d %d:%d %d:%d\n", srcPeg1, depth1, srcPeg2, depth2, dstPeg, depth3);
  174.     callDepth++;
  175.   #endif
  176.     if (depth1 || depth2) {
  177.         int largestPos1;
  178.         int largest1 = peg(srcPeg1).largestDisk(depth1, largestPos1);
  179.         int largest2 = depth2 ? peg(srcPeg2).diskAtDepth(depth2-1) : -1;
  180.         int largest3 = depth3 ? peg(dstPeg).diskAtDepth(depth3-1) : -1;
  181.         if (largest3 > largest1 && largest3 > largest2)
  182.             moveTower(srcPeg1, srcPeg2, dstPeg, depth1, depth2, depth3-1);
  183.         else if (largest2 > largest1 && largest2 > largest3)
  184.             if (peg(srcPeg1).ordered(depth1)) {
  185.                 moveTower(srcPeg2, dstPeg, srcPeg1, depth2-1, depth3, depth1);
  186.                 moveDisk(srcPeg2, dstPeg);
  187.                 moveTower(srcPeg2, srcPeg1, dstPeg, 0, depth2-1+depth3+depth1, 0);
  188.             } else {
  189.                 moveTower(srcPeg1, srcPeg2, dstPeg, depth1, depth2-1, depth3);
  190.                 moveTower(srcPeg2, dstPeg, srcPeg1, 0, depth1+depth2+depth3-1, 0);
  191.                 moveDisk(srcPeg2, dstPeg);
  192.                 moveTower(srcPeg2, srcPeg1, dstPeg, 0, depth1+depth2+depth3-1, 0);
  193.             }
  194.         else {
  195.             moveTower(srcPeg1, dstPeg, srcPeg2, largestPos1, depth3, depth2);
  196.             moveDisk(srcPeg1, dstPeg);
  197.             moveTower(srcPeg1, srcPeg2, dstPeg, depth1-largestPos1-1, largestPos1+depth3+depth2, 0);
  198.         }
  199.     }
  200.   #ifdef DEBUG
  201.     callDepth--;
  202.   #endif
  203. }
  204.  
  205.  
  206. pascal OSErr HowerOfTanoi( const FSSpec* infile, const FSSpec* outfile )
  207. {
  208.     Emitter *emitter = new Emitter;
  209.     
  210.     short inRef;
  211.     FSpOpenDF(infile, fsRdPerm, &inRef);
  212.     emitter->pegs[0] = ReadTower(inRef);
  213.     emitter->pegs[1].length = 0;
  214.     emitter->pegs[2].length = 0;
  215.     FSClose(inRef);
  216.     
  217.     FSpCreate(outfile, 'CWIE', 'TEXT', 0);
  218.     FSpOpenDF(outfile, fsCurPerm, &outRef);
  219.     
  220.     emitter->moveTower(1, 2, 3, emitter->pegs[0].length, 0, 0);
  221.     
  222.     FSClose(outRef);
  223.     delete emitter;
  224.  
  225.     return noErr;
  226. }
  227.